1. Field of the Invention
The invention disclosed and claimed herein generally pertains to a method and apparatus for selecting dependent instructions in an out of order issue queue for issue out of the queue. More particularly, the invention pertains to a method of the above type that allows back to back issue of dependent instructions. Even more particularly, the invention pertains to a method of the above type that allows multiple instructions to be considered during a cycle of the queue, so that one of them can be selected for issue out of the queue during the very next cycle.
2. Description of the Related Art
As is well known by those of skill in the computer arts, instructions are placed in an issue queue during successive cycles, for sequential issue and execution. However, in an out of order issue queue, some of the instructions can be selected for issue ahead of older or earlier instructions. As is further well known, currently available out of order issue queues generally allow dependent instructions to issue no more frequently than every other cycle, and thus do not support back to back issue of dependent instructions. A dependent instruction is one that must wait for issue and execution of an earlier instruction, in order to ensure that essential data required by the dependent instruction will be available. Back to back issue refers to issue of instructions from the queue during each of two consecutive cycles of queue operation.
To illustrate an out of order issue queue of currently available design, the following code sequence may be considered:
1) Add 1,x,x,
2) Add x,1,x
The out of order issue queue of the current design will take three cycles to issue both of these instructions, following initial selection of instruction 1. The timing diagram for this queue, showing successive pipeline stages, is as follows:
cycle01231)add 1, x, xselectissue2)add x, 1, xcmpselectissue
Instruction 1 is selected to issue during cycle 0, and is actually issued during cycle 1. Also during cycle 1, all instructions in the issue queue resolve dependencies, through destination to source compares. From this effort, it is determined that a source register of instruction 2 matches the target destination register of instruction 1. Accordingly, the source of instruction 2 is set to ready, to indicate that data needed for instruction 2 will be available. In cycle 2 instruction 2 is selected for issue, and during cycle 3 instruction 2 issues.
To improve on the above current design, and to thereby avoid wasted cycle time, it would be beneficial to provide an out of order issue queue in which back to back issue of dependent instructions is allowed to occur. In particular, it would clearly be beneficial to have instruction 2 selected during cycle 1 rather than cycle 2, so that instruction 2 would issue during cycle 2 instead of during cycle 3. This would reduce the issue time by an entire cycle. However, while some solutions have previously been proposed to achieve back to back issue, such solutions have typically required substantial hardware. For example, some of the proposed solutions pre-calculate all the dependencies of an instruction as it is placed into an issue queue. This requires a large number of compares and latches, in order to hold the pre-calculated state.
It would thus be desirable to provide an out of order issue queue that supported back to back issue of dependent instructions, and at the same time required only minimal amounts of additional hardware.